#include <iostream>
#include <vector>

using namespace std;

// https://leetcode.cn/problems/surrounded-regions/
// 130.

class Solution
{
public:
    void dfs(vector<vector<char>> &board, int row, int col, char ch)
    {
        if (row < 0 || row > board.size() - 1 || col < 0 || col > board[0].size() - 1 || board[row][col] != 'O')
        {
            return;
        }
        board[row][col] = ch;
        dfs(board, row + 1, col, ch);
        dfs(board, row - 1, col, ch);
        dfs(board, row, col - 1, ch);
        dfs(board, row, col + 1, ch);
    }
    
    void solve(vector<vector<char>> &board)
    {
        row = board.size();
        col = board[0].size();
        // 
        for (int edge = 0; edge < row; edge++)
        {
            if (board[edge][0] == 'O')
            {
                dfs(board, edge, 0, 'T');
            }
            if (board[edge][col - 1] == 'O')
            {
                dfs(board, edge, col - 1, 'T');
            }
        }
        for (int edge = 0; edge < col; edge++)
        {
            if (board[0][edge] == 'O')
            {
                dfs(board, 0, edge, 'T');
            }
            if (board[row - 1][edge] == 'O')
            {
                dfs(board, row - 1, edge, 'T');
            }
        }

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == 'O')
                {
                    dfs(board, i, j, 'X');
                }
                if (board[i][j] == 'T')
                {
                    board[i][j] = 'O';
                }
            }
        }
    }

private:
    int row = 0;
    int col = 0;
    vector<pair<int, int>> remove{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
};

int main()
{
    vector<vector<char>> board = {
        {'X', 'X', 'X', 'X'},
        {'X', 'O', 'O', 'X'},
        {'X', 'X', 'O', 'X'},
        {'X', 'O', 'X', 'X'}};

    Solution sol;
    sol.solve(board);

    // 输出结果
    for (const auto &row : board)
    {
        for (char c : row)
        {
            cout << c << " ";
        }
        cout << endl;
    }
    return 0;
}